package com.sicheng.lc.周赛.分类.思维.多路归并构造有序链表;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/10 22:36
 */
public class 子数组和排序后的区间和 {
    //https://leetcode.cn/problems/range-sum-of-sorted-subarray-sums/
    static int mod = (int) 1e9 + 7;

    public int rangeSum(int[] nums, int n, int left, int right) {
        // 定义比较规则
        Queue<int[]> q = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        // 加入头节点
        // 头节点包含两个值：子数组和，子数组的右边界
        for (int i = 0; i < n; i++) q.offer(new int[]{nums[i], i});
        int ans = 0;
        for (int i = 1; i <= right; i++) {
            int[] cur = q.poll();
            assert cur != null;
            int sum = cur[0], j = cur[1];
            // 开始记录结果
            if (i >= left) ans = (ans + sum) % mod;
            // 如果 j + 1 < n 表示该条链条后面还有元素，可以继续加入队列中
            if (j + 1 < n) q.offer(new int[]{sum + nums[j + 1], j + 1});
        }
        return ans;
    }
}
